package net.tp.algo.scheduling;

import java.util.Arrays;

/**
 * <p>Minimum Weighted Completion Time.</p>
 *
 *
 *
 * @author Trung Phan
 *
 */
public class WeightedCompletion {

    /**
     * <p>Schedule for simple min weighted completion time problem.</p>
     *
     * <p>The problem</p>
     * <ul>
     *  <li>$n$ jobs are scheduled on a shared machine</li>
     *  <li>Each job has length $l_i$ and weight/priority $w_i$</li>
     *  <li>Completion time $C_i$ for a job is the time lapsed until the job is completed</li>
     *  <li>Goal: miminize weighted completion time $∑ w_iC_i$.
     * </ul>
     *
     * <p>If all the jobs have the same length, then by common sense, the higher weight job should be scheduled first. If all jobs have the same weight, then then shorter job should be scheduled first. Given both length and weight are different among jobs, we are trying to prioritize jobs with shorter length and higher weight. The problem can be solved using greedy approach: schedule jobs in the order of $l_i / w_i$.</p>
     *
     * @author Trung Phan
     * @param lengths job's length
     * @param weights job's weight/priority
     * @return the schedule for jobs
     *
     */
    public static int[] schedule(final double[] lengths, final double[] weights) {
        int N = lengths.length;
        if (weights.length != N) throw new IllegalArgumentException("lengths and weights do not have equal size");

        Integer[] result = new Integer[N];
        for (int i = 0; i < N; i++) result[i] = i;

        Arrays.sort(result, (p, q) -> Double.compare(lengths[p] / weights[p], lengths[q] / weights[q]));

        int[] _result = new int[N];
        for (int i = 0; i < N; i++) _result[i] = result[i];

        return _result;
    }



}
